package Array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 56：合并区间
 *
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 *
 * 思路：
 * 1： 先对数组intervals进行排序，排序的字段是各区间的首位元素
 * 2： 遍历intervals数组，对每个区间进行合并，合并的规则是：
 *    遍历排序后的区间列表，对于每个区间，如果它的起始位置在结果列表的最后一个区间的结束位置之后，说明它和之前的所有区间都不重叠，
 *    可以直接添加到结果列表中。否则，它与结果列表的最后一个区间重叠，此时我们需要更新结果列表中最后一个区间的结束位置，使其能够覆盖当前区间。
 * 3： 合并完所有区间后，返回合并后的区间数组
 *
 * 具体步骤：
 * 1： 循环排序int[][]数组intervals，排序的字段是intervals[i][0]
 * 2： 定义int[][] mergedIntervals = new int[intervals.length][2]，用于存储合并后的区间
 * 3： 定义int index = 0，用于记录合并后的区间的个数
 * 4： 循环遍历intervals数组，对每个区间进行合并
 *    a： 如果当前区间的首位元素大于等于上一个区间的尾部元素，则合并，否则跳过
 *    b： 合并的规则是：mergedIntervals[index][0] = Math.min(mergedIntervals[index-1][0], intervals[i][0])，
 *       mergedIntervals[index][1] = Math.max(mergedIntervals[index-1][1], intervals[i][1])
 *    c： index++，记录合并后的区间的个数
 * 5： 返回mergedIntervals数组
 */
public class MergeArray {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }
        // 1: 对数组进行排序
        Arrays.sort(intervals, Comparator.comparing(a -> a[0]));
        // 2: 定义返回的数组
        List<int[]> result = new ArrayList<>();
        result.add(intervals[0]); // 添加首位
        //3: 遍历数组,进行比较
        for (int i = 1; i < intervals.length; i++) {
            // 获取上一个区间
            int[] lastInterval = result.get(result.size() - 1);
            // 获取当前区间
            int[] currentInterval = intervals[i];
            // 如果当前区间的首位小于等于上一个区间的末位，则可以合并(更新末位),
            // 因为是新数组，lastInterval已经添加到result中，所以合并即可
            if(currentInterval[0] <= lastInterval[1]){
                lastInterval[1] = Math.max(lastInterval[1],currentInterval[1]);
            }else{
                // 如果没有重叠，则添加当前区间到列表
                result.add(currentInterval);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}
